package com.cqs.leetcode;

/**
 * Union Find　算法求解
 */
public class FriendCircles547 {


    class UnionFind {
        int[] ids;
        int count;

        public UnionFind(int len) {
            ids = new int[len];
            for (int i = 0; i < len; i++) {
                ids[i] = i;
            }
            count = len;
        }

        public int find(int p) {
            while (p != ids[p]) {
                p = ids[p];
            }
            return p;
        }

        public void union(int p, int q) {
            int idp = find(p);
            int idq = find(q);
            if (idp == idq) return;
            for (int i = 0; i < ids.length; i++) {
                if (ids[i] == idq) ids[i] = p;
            }
            --count;
        }
    }

    //
    public int findCircleNum(int[][] M) {
        //点的个数
        int len = M.length;
        UnionFind uf = new UnionFind(len);
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (M[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }

        return uf.count;
    }

    //
    public static void main(String[] args) {
        int[][] a = {{1, 1, 0},
                {1, 1, 0},
                {0, 0, 1}};
        FriendCircles547 friend = new FriendCircles547();
        int circleNum = friend.findCircleNum(a);
        System.out.println(circleNum);
    }
}
